package base.sort;

import base.utils.PrintUtils;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * 插入排序最大的弊端就是太依赖于要排序数组的有序性，排序数组越有序，他排序时间越短,越无序时间越长.
 *
 * 希尔排序是他的升级版,希尔排序先让数组部分有序,最后再将h设为1,
 * 从而实现全部有序.他权衡了数组的规模性还有有序性,对大型数组,任意排列的数组表现都很好.
 *
 * https://www.runoob.com/w3cnote/shell-sort.html
 *
 * https://www.cnblogs.com/chengxiao/p/6104371.html
 */
public class ShellSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int gap = 1;
        while (gap < arr.length) {
            gap = gap * 3 + 1;
            PrintUtils.print( "gap = "+ gap);
        }

//        PrintUtils.print( "gap = "+ gap + "; arr.length = " + arr.length);

        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }

        return arr;
    }


    /**
     * 这里为比较容易理解
     */
    public static void mySort(){

        int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};

        //希尔排序
        int gap = array.length;

        while (true) {
            gap = gap/ 2;                                               //增量每次减半,

            for (int i = 0; i < gap; i++) {

                for (int j = i + gap; j < array.length; j += gap) {     //这个循环里其实就是一个插入排序

                    int temp = array[j];
                    int k = j - gap;                                    //相当于得到  i (j=i+gap)

                    while (k >= 0 && array[k] > temp) {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = temp;
                }

            }

            if (gap == 1) break;
        }

    }

    public static void shellSortPiece(int[] arr) {
        //希尔排序
        int gap = arr.length;
        int len = arr.length;
        while (true) {
            gap = gap / 2;
            for (int i=0;i<gap;i++){
                for (int j=i;j<len;j+=gap){
                    int tmp=arr[j];
                    int k=j;
                    while (k>gap-1&&arr[k-gap]>tmp){        //gap最小为1，即k>0;
                        arr[k]=arr[k-gap];
                        k-=gap;
                    }
                    if (k!=j)arr[k]=tmp;
                }
            }
            if (gap == 1) break;
        }
    }



}
